import java.util.*;

public class Main3 {
    /**
     * 二叉树
     */
    public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
  }

    /**
     * 前序遍历
     */
    public void preorder(List<Integer> list, TreeNode root) {
        if(root == null) {
            return;
        }
        list.add(root.val);
        preorder(list, root.left);
        preorder(list, root.right);
    }
    public int[] preorderTraversal (TreeNode root) {
        // write code here
        List<Integer> list = new ArrayList<>();
        preorder(list, root);
        int[] arr = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }
    /**
     * 中序遍历
     */
    public void inorder(List<Integer> list, TreeNode root) {
        if(root == null) {
            return;
        }
        inorder(list,root.left);
        list.add(root.val);
        inorder(list, root.right);
    }
    public int[] inorderTraversal (TreeNode root) {
        // write code here
        List<Integer> list = new ArrayList<>();
        inorder(list, root);
        int[] ret = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }
    /**
     * 后序遍历
     */
    public void postorder(List<Integer> list, TreeNode root) {
        if(root == null) {
            return;
        }
        postorder(list, root.left);
        postorder(list, root.right);
        list.add(root.val);
    }
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        List<Integer> list = new ArrayList<>();
        postorder(list, root);
        int[] ret = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }

    /**
     * 层次遍历
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            //记录二叉树的某一行
            ArrayList<Integer> row = new ArrayList<>();
            int n = queue.size();
            //因先进入的是根结点，故每层节点多少，队列大小就是多少
            for(int i = 0; i < n; i++) {
                TreeNode cur = queue.poll();
                row.add(cur.val);
                //若是左右孩子存在，则存在左右孩子作为下一个层次
                if(cur.left != null) {
                    queue.add(cur.left);
                }
                if(cur.right != null) {
                    queue.add(cur.right);
                }
            }
            //每一层加入输出
            list.add(row);
        }
        return list;
    }

    /**
     * 按之字形顺序打印二叉树
     */
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        // write code here
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        TreeNode head = pRoot;
        if(head == null) {
            return list;
        }
        //队列存储，进行层次遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(head);
        TreeNode p;
        boolean flg = true;
        while(!queue.isEmpty()) {
            //记录二叉树的某一行
            ArrayList<Integer> row = new ArrayList<>();
            int n = queue.size();
            //奇数行反转，偶数行不反转
            flg = !flg;
            //因先进入的是根结点，故每层节点多少，队列大小就是多少
            for(int i = 0; i < n; i++) {
                p = queue.poll();
                row.add(p.val);
                //若是左右孩子存在，则存入左右孩子作为下一层次
                if(p.left != null) {
                    queue.offer(p.left);
                }
                if(p.right != null) {
                    queue.offer(p.right);
                }
            }
            //奇数行进行反转，偶数行不反转
            if(flg) {
                Collections.reverse(row);
            }
            list.add(row);
        }
        return list;
    }
    public ArrayList<ArrayList<Integer>> Print2 (TreeNode pRoot) {
        // write code here
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        TreeNode head = pRoot;
        if(head == null) {
            return list;
        }
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        //放入第一行
        s1.push(head);
        while(!s1.isEmpty() || !s2.isEmpty()) {
            ArrayList<Integer> tmp = new ArrayList<>();
            //遍历奇数层
            while(!s1.isEmpty()) {
                TreeNode node = s1.pop();
                //记录奇数层
                tmp.add(node.val);
                //奇数层的子节点加入偶数层
                if(node.left != null) {
                    s2.push(node.left);
                }
                if(node.right != null) {
                    s2.push(node.right);
                }
            }
            //数组不为空才添加
            if(tmp.size() != 0) {
                list.add(new ArrayList<Integer>(tmp));
            }
            //清除本层数据
            tmp.clear();
            //遍历偶数层
            while(!s2.isEmpty()) {
                TreeNode node = s2.pop();
                //记录偶数层
                tmp.add(node.val);
                //偶数层的子节点加入奇数层
                if(node.right != null) {
                    s1.push(node.right);
                }
                if(node.left != null) {
                    s1.push(node.left);
                }
            }
            //数组不为空才添加
            if(tmp.size() != 0) {
                list.add(new ArrayList<Integer>(tmp));
            }
            //清除本层数据
            tmp.clear();
        }

        return list;
    }


    /**
     * 二叉树的最大深度
     */
    public int maxDepth (TreeNode root) {
        // write code here
        if(root == null) {
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        return (leftHeight > rightHeight ? leftHeight : rightHeight) +1;
    }
    public int maxDepth2 (TreeNode root) {
        // write code here
        if(root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        int ret = 0;
        queue.add(root);
        //遍历每一层
        while(!queue.isEmpty()) {
            int size = queue.size();
            //遍历当前层每个节点
            for(int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            //记录层数
            ret++;
        }
        return ret;
    }

    /**
     * 二叉树中和为某一值的路径(一)
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if(root == null) {
            return false;
        }
        //栈辅助深度优先遍历
        Stack<TreeNode> s1 = new Stack<>();
        //跟随s1记录到相应节点为止的路径和
        Stack<Integer> s2 = new Stack<>();
        s1.push(root);
        s2.push(root.val);
        while(!s1.isEmpty()) {
            //弹出相应节点
            TreeNode node = s1.pop();
            //弹出到该点为止的当前路径和
            int cur_sum = s2.pop();
            //叶子节点且当前路径和等于sum
            if(node.left == null && node.right == null && cur_sum == sum){
                return true;
            }
            //左节点及路径和入栈
            if(node.left != null) {
                s1.push(node.left);
                s2.push(cur_sum + node.left.val);
            }
            //右节点及路径和入栈
            if(node.right != null) {
                s1.push(node.right);
                s2.push(cur_sum + node.right.val);
            }
        }
        return false;
    }
    public boolean hasPathSum2 (TreeNode root, int sum) {
        // write code here
        if(root == null) {
            return false;
        }
        //叶子节点，且路径和为sum
        if(root.left == null && root.right == null && sum - root.val == 0) {
            return true;
        }
        //递归进入子节点
        return hasPathSum(root.left,sum - root.val) || hasPathSum(root.right, sum - root.val);
    }

    /**
     * 二叉搜索树与双向链表
     */
    // 返回第一个指针，即为最小值，先定为Null
    public TreeNode head = null;
    //中序遍历当前值的上一位，初值为最小值，先定null
    public TreeNode pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            //中序递归，叶子为空则返回
            return null;
        }
        //首先递归到最左最小值
        Convert(pRootOfTree.left);
        //找到最小值，初始化head 和 pre
        if(pre == null) {
            head = pRootOfTree;
            pre = pRootOfTree;
        }else {
            // 当前节点与上一节点建立联系，将pre 设置为当前值
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return head;
    }
    public TreeNode Convert1(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            //中序递归，叶子为空则返回
            return null;
        }
        Stack<TreeNode> s = new Stack<TreeNode>();
        TreeNode head = null;
        TreeNode pre = null;
        //确定第一个遍历到最左，即为首位
        boolean isFirst = true;
        while(pRootOfTree != null || !s.isEmpty()) {
            //直到没有左节点
            while(pRootOfTree != null) {
                s.push(pRootOfTree);
                pRootOfTree = pRootOfTree.left;
            }
            pRootOfTree = s.pop();
            //最左元素即表头
            if(isFirst) {
                head = pRootOfTree;
                pre = head;
                isFirst = false;
            }else {
                //当前节点与上一节点建立连接,将pre 设置成当前值
                pre.right = pRootOfTree;
                pRootOfTree.left = pre;
                pre = pRootOfTree;
            }
            pRootOfTree = pRootOfTree.right;
        }
        return head;
    }

    /**
     * 对称的二叉树
     */
    public boolean recursion(TreeNode root1, TreeNode root2) {
        //可以两个都为空
        if(root1 == null && root2 == null) {
            return true;
        }
        //只有一个为空或者节点值不同，必不对称
        if(root1 == null || root2 == null || root1.val != root2.val) {
            return false;
        }
        return recursion(root1.left, root2.right) && recursion(root1.right, root2.left);
    }
    public boolean isSymmetrical (TreeNode pRoot) {
        // write code here

        return recursion(pRoot, pRoot);

    }
    public boolean isSymmetrical2 (TreeNode pRoot) {
        // write code here
        if(pRoot == null) {
            return true;
        }
        //辅助队列用于从两边层次遍历
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        q1.offer(pRoot.left);
        q2.offer(pRoot.right);
        while(!q1.isEmpty() && !q2.isEmpty()) {
            //分别从左边和右边弹出节点
            TreeNode left = q1.poll();
            TreeNode right = q2.poll();
            //都为空暂时对称
            if(left == null && right == null) {
                continue;
            }
            //某一个为空或者数字不相等则不对称
            if(left == null || right == null || left.val != right.val) {
                return false;
            }
            //从左往右加入队列
            q1.offer(left.left);
            q1.offer(left.right);
            //从右往左加入队列
            q2.offer(right.right);
            q2.offer(right.left);
        }
        return true;


    }
    /**
     * 合并二叉树
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        if(t1 == null) {
            return t2;
        }
        if(t2 == null) {
            return t1;
        }
        TreeNode head = new TreeNode(t1.val + t2.val);
        head.left = mergeTrees(t1.left, t2.left);
        head.right = mergeTrees(t1.right, t2.right);
        return head;
    }
    public TreeNode mergeTrees2 (TreeNode t1, TreeNode t2) {
        // write code here
        if(t1 == null) {
            return t2;
        }
        if(t2 == null) {
            return t1;
        }
        TreeNode head = new TreeNode(t1.val + t2.val);
        Queue<TreeNode> q = new LinkedList<>();
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        q.offer(head);
        q1.offer(t1);
        q2.offer(t2);
        while(!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode node = q.poll();
            TreeNode node1 = q1.poll();
            TreeNode node2 = q2.poll();
            TreeNode left1 = node1.left;
            TreeNode left2 = node2.left;
            TreeNode right1 = node1.right;
            TreeNode right2 = node2.right;
            if(left1 != null || left2 != null) {
                // 两个左节点都存在
                if(left1 != null && left2 != null) {
                    TreeNode left = new TreeNode(left1.val + left2.val);
                    node.left = left;
                    //新节点入队列
                    q.offer(left);
                    q1.offer(left1);
                    q2.offer(left2);
                }else if(left1 != null) {
                    node.left = left1;
                }else {
                    node.left = left2;
                }
            }
            if(right1 != null || right2 != null) {
                //两个右节点都存在
                if(right1 != null && right2 != null) {
                    TreeNode right = new TreeNode(right1.val + right2.val);
                    node.right = right;
                    //新节点入队列
                    q.offer(right);
                    q1.offer(right1);
                    q2.offer(right2);
                }else if(right1 != null) {
                    node.right = right1;
                }else {
                    node.right = right2;
                }
            }

        }


        return head;
    }
    /**
     * 二叉树的镜像
     */
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        if(pRoot == null) {
            return pRoot;
        }
        //先递归子树
        TreeNode left = Mirror(pRoot.left);
        TreeNode right = Mirror(pRoot.right);
        //交换
        pRoot.left = right;
        pRoot.right = left;
        return pRoot;
    }

    /**
     * 判断是不是二叉搜索树
     */
    int pre1 = Integer.MIN_VALUE;
    public boolean isValidBST (TreeNode root) {
        // write code here
        if(root == null) {
            return true;
        }
        if(!isValidBST(root.left)) {
            return false;
        }
        if(root.val < pre1) {
            return false;
        }
        //更新最值
        pre1 = root.val;
        //再进入右子树
        return isValidBST(root.right);
    }
    public boolean isValidBST2 (TreeNode root) {
        // write code here
        Stack<TreeNode> s = new Stack<>();
        TreeNode head = root;
        ArrayList<Integer> sort = new ArrayList<>();
        while(head != null || !s.isEmpty()) {
            //直到没有左节点
            while(head != null) {
                s.push(head);
                head = head.left;
            }
            head = s.pop();
            //访问节点
            sort.add(head.val);
            //进入右边
            head = head.right;
        }
        //遍历中序结果
        for(int i = 1; i < sort.size(); i++) {
            //一旦降序，则不是搜索树
            if(sort.get(i - 1) > sort.get(i)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 判断是不是完全二叉树
     */
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        if(root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while(!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if(tmp != null) {
                return false;
            }
        }
        return true;
    }

    /**
     * 判断是不是平衡二叉树
     */
    public int deep(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = deep(root.left);
        int right = deep(root.right);
        return (left > right) ? left + 1 : right + 1;
    }
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        // write code here
        if(pRoot == null) {
            return true;
        }
        int left = deep(pRoot.left);
        int right = deep(pRoot.right);

        if(left - right > 1 || left - right < -1) {
            return false;
        }

        return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
    }

    /**
     * 二叉搜索树的最近公共祖先
     */
    //求得根节点到目标节点的路径
    public ArrayList<Integer> getPath(TreeNode root, int target) {
        ArrayList<Integer> path = new ArrayList<Integer>();
        TreeNode node = root;
        //节点值都不同，可以直接用值比较
        while (node.val != target) {
            path.add(node.val);
            //小的在左子树
            if (target < node.val)
                node = node.left;
                //大的在右子树
            else
                node = node.right;
        }
        path.add(node.val);
        return path;
    }
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        //求根节点到两个节点的路径
        ArrayList<Integer> path_p = getPath(root, p);
        ArrayList<Integer> path_q = getPath(root, q);
        int res = 0;
        //比较两个路径，找到第一个不同的点
        for (int i = 0; i < path_p.size() && i < path_q.size(); i++) {
            int x = path_p.get(i);
            int y = path_q.get(i);
            //最后一个相同的节点就是最近公共祖先
            if (x == y)
                res = path_p.get(i);
            else
                break;
        }
        return res;
    }
    public int lowestCommonAncestor2 (TreeNode root, int p, int q) {
        //空树找不到公共祖先
        if(root == null) {
            return -1;
        }
        //pq在该节点两边说明这就是最近公共祖先
        if((p >= root.val && q < root.val) || (p <= root.val && q >= root.val)) {
            return root.val;
        }else if(p <= root.val && q <= root.val) {
            //pq都在该节点的左边
            //进入左子树
            return lowestCommonAncestor(root.left, p, q);
        }else {
            //pq都在该节点的右边
            //进入右子树
            return lowestCommonAncestor(root.right, p, q);
        }
    }

    /**
     * 在二叉树中找到两个节点的最近公共祖先
     */
    public boolean flg = false;
    public void dfs(TreeNode root, ArrayList<Integer> path, int o) {
        if(flg || root == null) {
            return;
        }
        path.add(root.val);
        if(root.val == o) {
            flg = true;
            return;
        }
        dfs(root.left,path,o);
        dfs(root.right,path,o);
        //找到
        if(flg) {
            return;
        }
        //回溯
        path.remove(path.size()-1);
    }
    public int lowestCommonAncestor3 (TreeNode root, int o1, int o2) {
        // write code here
        ArrayList<Integer> path1 = new ArrayList<>();
        ArrayList<Integer> path2 = new ArrayList<>();
        //求根结点到两个节点的路径
        dfs(root, path1, o1);
        flg = false;
        dfs(root, path2, o2);
        int ret = 0;
        //比较两个路径，找到第一个不同的点
        for(int i = 0; i < path1.size() && i < path2.size(); i++) {
            int x = path1.get(i);
            int y = path2.get(i);
            if(x == y) {
                //最后一个相同的节点就是最近公共祖先
                ret = x;
            }else {
                break;
            }
        }

        return ret;
    }
    public int lowestCommonAncestor4 (TreeNode root, int o1, int o2) {
        // write code here
        if(root == null) {
            return -1;
        }
        //该节点是其中某一个节点
        if(root.val == o1 || root.val == o2) {
            return root.val;
        }
        //左子树寻找公共祖先
        int left = lowestCommonAncestor4(root.left, o1, o2);
        //右子树寻找公共祖先
        int right = lowestCommonAncestor4(root.right, o1, o2);
        //左子树没找到，则在右子树中
        if(left == -1) {
            return right;
        }
        //右子树没找到，则在左子树中
        if(right == -1) {
            return left;
        }
        return root.val;
    }

    /**
     * 重建二叉树
     */
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        // write code here
        int n = preOrder.length;
        int m = vinOrder.length;
        //每个遍历都不能为0
        if (n == 0 || m == 0)
            return null;
        //构建根节点
        TreeNode root = new TreeNode(preOrder[0]);
        for (int i = 0; i < vinOrder.length; i++) {
            //找到中序遍历中的前序第一个元素
            if (preOrder[0] == vinOrder[i]) {
                //构建左子树
                root.left = reConstructBinaryTree(Arrays.copyOfRange(preOrder, 1, i + 1),
                        Arrays.copyOfRange(vinOrder, 0, i));
                //构建右子树
                root.right = reConstructBinaryTree(Arrays.copyOfRange(preOrder, i + 1, preOrder.length),
                        Arrays.copyOfRange(vinOrder, i + 1, vinOrder.length));
                break;
            }
        }
        return root;
    }



}


